/*
 * @Author: liusheng
 * @Date: 2022-06-26 16:09:18
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-26 19:16:23
 * @Description: 
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 084. 含有重复元素集合的全排列 
给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

 

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10
 

注意：本题与主站 47 题相同： https://leetcode-cn.com/problems/permutations-ii/

通过次数12,949   提交次数18,744
 */

#include "header.h"

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        vector<bool> visited(nums.size(),false);
        sort(nums.begin(),nums.end());
        vector<int> prefix;
        permuteUnique(nums,0,nums.size(),visited,prefix,result);
        return result;
    }
private:
    void permuteUnique(vector<int>& nums,int curIndex,int totalSize,vector<bool> & visited,vector<int> &prefix,vector<vector<int>> &result)
    {
        if (curIndex == totalSize)
        {
            result.emplace_back(prefix);
            return;
        }
        
        for (int i = 0; i < totalSize; ++i)
        {
            //!visited[i-1] means not in trace back procedure
            /*
            这个判断条件保证了对于重复数的集合，一定是从左往右逐个填入的。
            假设我们有 3 个重复数排完序后相邻，那么我们一定保证每次都是拿从左往右
            第一个未被填过的数字，即整个数组的状态其实是保证了 [未填入，未填入，未填入]
            [未填入，未填入，未填入] 到 [填入，未填入，未填入][填入，未填入，未填入]，
            再到 [填入，填入，未填入][填入，填入，未填入]，最后到 [填入，填入，填入][填入，填入，填入] 
            的过程的，因此可以达到去重的目标。

            */
            if (visited[i] || (i > 0 && nums[i] == nums[i-1] && !visited[i-1]))
            {
                continue;
            }
            
            visited[i] = true;
            prefix.push_back(nums[i]);
            
            permuteUnique(nums,curIndex + 1,totalSize,visited,prefix,result);
            prefix.pop_back();
            
            visited[i] = false;
        }
    }
    
};

/*
using hash to keep unique
*/
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        permute(nums,0,nums.size(),result);
        return result;
    }
private:
    void permute(vector<int>& nums,int curIndex,int totalSize,vector<vector<int>> & result)
    {
        if (curIndex == totalSize - 1)
        {
            long hashVal = hashPermute(nums);
            if (!visited.count(hashVal))
            {
                result.emplace_back(nums);
                visited.insert(hashVal);
            }
        }

        for (int i = curIndex; i < totalSize; ++i)
        {
            swap(nums[i],nums[curIndex]);
            permute(nums,curIndex + 1,totalSize,result);
            //back trace
            swap(nums[i],nums[curIndex]);
        }
    }
private:
    long hashPermute(vector<int>& nums)
    {
        long result = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            result |= ((long)nums[i] + 10) << (i * 6);
        }
        return result;
    }
private:   
    unordered_set<long> visited;
};
